
//41.缺失的第一个正数
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //有1-n个数据，其正数最大的情况就是1-n中每个数nums中都存在
        //将1-n中的每个数都交换到对应的位置，最后遍历数组第一个下标+1与数值不相等的位置就是答案
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int x=nums[i];
            while(x<=n&&x>0&&nums[x-1]!=nums[i])   //不在区间的数值不需要进行交换，数值与下标位置已经对应不进行交换
            {
                swap(nums[i],nums[x-1]);   //将对应数值交换到对应下标位置
                x=nums[i];         //看交换来的位置是否还需要进行交换
            }
        }
        for(int i=0;i<n;i++) 
            if(nums[i]!=i+1) return i+1;  //找下标与数值不对应的位置
        
        return n+1;
    }
};